package JZ_Offer.algorithm.dp;

/**
 * 斐波那契数列
 *
 * 大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项为1，n<=39）
 *
 * @Author piper
 * @Date 2019/11/11 3:03 下午
 */
public class JZ10_斐波那契数列 {
    /**
     * 递归实现
     */
    static int Fibonacci(int n) {
        if (n < 3) return n;
        int l2 = 2, l1 = 1, res = 0;
        for (int i = 3; i <= n; i++) {
            res = l2 + l1;
            l1 = l2;
            l2 = res;
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(Fibonacci(7));
    }
}
